from offer.data_structure import BinaryTreeNode


class Task37:
    def serialize(self, tree):
        preorder_list = []
        self.preorder(tree, preorder_list)
        return ','.join(preorder_list)

    def preorder(self, node, preorder_list):
        if node is None:
            preorder_list.append('$')
        else:
            preorder_list.append(str(node.val))
            self.preorder(node.left, preorder_list)
            self.preorder(node.right, preorder_list)

    def deserialize(self, string):
        preorder_list = string.split(',')
        return self.deserialize_inner(iter(preorder_list))

    def deserialize_inner(self, preorder_iter):
        symbol = next(preorder_iter)
        if symbol == '$':
            return None
        else:
            node = BinaryTreeNode(int(symbol))
            node.left = self.deserialize_inner(preorder_iter)
            node.right = self.deserialize_inner(preorder_iter)
            return node
